#pragma once
#include<iostream>
#include<string>

#include "../common/read.h"

#define ll long long
#define INF 10000

using namespace std;
int tot=1,ans=0;

//最大流的节点定影
struct MNode
{
    int to;//表示有向边的箭头
    int net;//有向边的起点
    int val;
};

//马氏距离匹配节点结构
struct ma_node
{
    double maScore;
    int index1,index2;
    ma_node(double maScore,int index1,int index2):
        maScore(maScore),index1(index1),index2(index2){}
    //定义从小到大排序    
    bool operator<(const ma_node& o) const {
		return o.maScore < maScore;
	}
};

/**
 * @brief 添加正向和反向边
 * 
 * @param e //对应边集合
 * @param u 
 * @param v 
 * @param w 
 */
inline void addEdge1(vector<MNode>& e,vector<int>& head,int u,int v,int w){
    MNode temp;
    //正向边
    ++tot;
    temp.to=v;
    temp.val=w;
    temp.net=head[u];
    head[u]=tot;
    e.push_back(temp);
    //反向边
    ++tot;
    temp.to=u;
    temp.val=0;
    temp.net=head[v];
    head[v]=tot;
    e.push_back(temp);
    // e[++tot].to = v;
    // e[tot].val=w;
    // e[tot].net=head[u];
    // head[u]=tot;
    // e[++tot].to=u;


    // e[tot].val=0;
    // e[tot].net=head[v];
    // head[v]=tot;
}
/**
 * @brief 寻找增广路径
 * 
 * @param e 
 * @param dis 
 * @param pre 
 * @param vist 
 * @param head 
 * @param source 
 * @param sink 
 * @return int 
 */
inline int bfs1(vector<MNode>& e, vector<int>& dis,vector<int>&pre, vector<int>& vist,vector<int>& head,int& source,int& sink){
    vist.assign(vist.size(),0);
    int x,v;
    queue<int>q;
    q.push(source);
    vist[source]=1;
    dis[source]=INF;
    while (!q.empty())
    {
        x = q.front();//获取队列头部
        q.pop();
        for (int i = head[x]; i ; i=e[i].net )
        {
            if(e[i].val==0) continue;//只关心流量剩余量大于0
            v=e[i].to;
            if(vist[v]==1) continue;//访问过就不访问了
            dis[v]=min(dis[x],e[i].val);
            pre[v]=i;//记录前驱，方便修改边权 
            q.push(v);
            vist[v]=1;//标记访问
            if(v==sink) return 1;//访问到源节点
        }
        
    }
    
    return 0;
}
/**
 * @brief 更新残差网络
 * 
 * @param e 
 * @param dis 
 * @param pre 
 * @param source 
 * @param sink 
 */
inline void update1(vector<MNode>&e,vector<int>& dis,vector<int>&pre, int& source,int& sink){
    int x =sink;
    int v,ind=0,wnum=0,indexW=-1,indexT=-1;
    wnum = mWorkers.size();
    while (x!=source)//从汇聚节点往源节点进行更新
    {
        v = pre[x];
        e[v].val-=dis[sink];
        e[v^1].val+=dis[sink];
        x=e[v^1].to;
        ind = e[v].to;
        //记录匹配成功的工作者和任务编号
        if ( ind > 1 && ind < wnum+2){
            indexW = ind-2;//减2恢复原来编号
        }else{
            indexT = ind-wnum-2;
        }
        if(indexW!=-1&&indexT!=-1){
            mWorkers[indexW]=indexT;
            mTasks[indexT] = indexW;
            indexW=-1;
            indexT=-1;
        }
    }
    ans+=dis[sink];
}

/**
 * @brief 直接使用扰动后的位置获取初始匹配
 * 
 * @param fileName 
 * @return int 
 */
int oblivious_M(string fileName){
    tot=1;
    ans=0;
    int workerNum,taskNum,sumNum;
    // read(fileName,workerNum,taskNum,sumNum);
    read2(fileName,workerNum,taskNum,sumNum);
    sumNum +=3;//两个1分别是最大流算法的源节点和汇合节点
    // vector<vector<int>>flag(sumNum,vector<int>(sumNum));//标记的二维数组
    vector<int>vist(sumNum,0);
    vector<int>dis(sumNum,0);
    vector<int>pre(sumNum,0);
    vector<int>head(sumNum,0);
    vector<MNode>e(2);
    mWorkers.resize(workerNum,-1);//初始化
    mTasks.resize(taskNum,-1);
    int source=1,sink=source+workerNum+taskNum+1;
    for (int i = 0; i < workerNum; i++)
    {
        addEdge1(e,head,source,i+2,1);
    }
    // vector<vector<double>> mahalanobisM(workerNum,vector<double>(taskNum,-1));
    // for (int i = 0; i < workerNum; i++){
    //     for (int j = 0; j < taskNum; j++){
    //         mahalanobisM[i][j] = calDistance3(perturbWorkers[i].loc,perturbTasks[j].loc);
    //     }
    // }
    // for (int w = 0; w < workerNum; w++){
    //     vector<double> tmp = mahalanobisM[w];
    //     int t = min_element(tmp.begin(),tmp.end())-tmp.begin();
    //     addEdge1(e,head,w+2,t+workerNum+1+1,1);
    // }
    for (int i = 0; i < workerNum; i++)
    {
        for (int j = 0; j < taskNum; j++)
        {
            if (satisfyDistanceTime(perturbWorkers[i],perturbTasks[j]))
            {
                addEdge1(e,head,i+2,j+workerNum+1+1,1);//0号不用，1号下表存源节点，因此二分图左边第一个点下标为i+2，右边节点的第一个下标j+workerNum+1+1
            }
        }
    }
    
    for (int i = 0; i < taskNum; i++)
    {
        addEdge1(e,head,i+workerNum+1+1,sink,1);
    }
    //开始匹配
    while (bfs1(e,dis,pre,vist,head,source,sink)!=0)
    {
        update1(e,dis,pre,source, sink);
    }
    // cout<<sink<<endl;
    // cout<<ans<<endl;
    // for (int i=0;i<32;i++){
	// 	cout<<i<<":";
	// 	cout<<e[i].to<<"\t";
	// 	cout<<e[i].val<<"\t";
	// 	cout<<e[i].net<<endl;
    // }
    // for (int i=0;i<=8;i++){
	// 	cout<<head[i]<<" ";
	// }
	// cout<<endl;
    // int nn = 0;
    // for (int i=0;i<workerNum;i++){
    //     if(satisfyDistanceTime(workerLists[i],taskLists[mWorkers[i]]))
    //         nn++;
    // }
    // cout<<"real:"<<nn<<endl;
    //获取最终匹配成功的对
    if(workerNum<taskNum){
        for(int i=0;i<workerNum;i++){
            if(mWorkers[i]!=-1){
                pair<int,int> m0;
                m0.first=i;
                m0.second=mWorkers[i];
                M0.push_back(m0);//记录匹配对
                // Xposition.push_back(perturbWorkers[m0.first].loc);
                // Xposition.push_back(perturbTasks[m0.second].loc);
            }            
        } 
    }else{
        for(int i=0;i<taskNum;i++){
            if(mTasks[i]!=-1){
                pair<int,int> m0;
                m0.first=mTasks[i];
                m0.second=i;
                M0.push_back(m0);//记录匹配对
                // Xposition.push_back(perturbWorkers[m0.first].loc);
                // Xposition.push_back(perturbTasks[m0.second].loc);
            }            
        } 
    }
    
    // cout<<"total:"<<M0.size()<<endl;

    return ans;
}

/**
 * @brief 根据匹配失败的工作者和任务多次迭代获取匹配对
 * 
 * @param failWorkers 
 * @param failTasks 
 * @return int 
 */
int oblivious_M(vector<int>&failWorkers,vector<int>&failTasks){
    tot=1;
    ans=0;
    int workerNum,taskNum,sumNum;
    workerNum = perturbWorkers.size();
    taskNum = perturbTasks.size();
    sumNum = workerNum+taskNum+3;//加3原因是0下标不用
    vector<int>vist(sumNum,0);
    vector<int>dis(sumNum,0);
    vector<int>pre(sumNum,0);
    vector<int>head(sumNum,0);
    vector<MNode>e(2);
    //先清除数据
    mWorkers.clear();
    mTasks.clear();
    mWorkers.resize(workerNum,-1);//初始化
    mTasks.resize(taskNum,-1);
    
    int source=1,sink=source+workerNum+taskNum+1,failWN,failTN;
    failWN = failWorkers.size();
    failTN = failTasks.size();
    for (int i = 0; i < failWN; i++)
    {
        addEdge1(e,head,source,failWorkers[i]+2,1);
    }
    for (int i = 0; i < failWN; i++)
    {
        int windex = failWorkers[i];
        for (int j = 0; j < failTN; j++)
        {
            int tindex = failTasks[j];
            if (satisfyDistanceTime(perturbWorkers[windex],perturbTasks[tindex]))
            {
                addEdge1(e,head,windex+2,tindex+workerNum+1+1,1);//0号不用，1号下表存源节点，因此二分图左边第一个点下标为i+2，右边节点的第一个下标j+workerNum+1+1
            }
            
        }

    }
    for (int i = 0; i < failTN; i++)
    {
        addEdge1(e,head,failTasks[i]+workerNum+1+1,sink,1);
    }
    //开始匹配
    while (bfs1(e,dis,pre,vist,head,source,sink)!=0)
    {
        update1(e,dis,pre,source, sink);
    }
    vector<pair<int,int>>().swap(M0);//清空原有数据
    // vector<pair<double,double>>().swap(Xposition);//记录所有匹配成功位置，计算马哈拉诺比斯距离
    //获取最终匹配成功的对
    if(workerNum<taskNum){
        for(int i=0;i<workerNum;i++){
            if(mWorkers[i]!=-1){
                pair<int,int> m0;
                m0.first=i;
                m0.second=mWorkers[i];
                M0.push_back(m0);//记录匹配对
                // Xposition.push_back(perturbWorkers[m0.first].loc);
                // Xposition.push_back(perturbTasks[m0.second].loc);
            }            
        } 
    }else{
        for(int i=0;i<taskNum;i++){
            if(mTasks[i]!=-1){
                pair<int,int> m0;
                m0.first=mTasks[i];
                m0.second=i;
                M0.push_back(m0);//记录匹配对
                // Xposition.push_back(perturbWorkers[m0.first].loc);
                // Xposition.push_back(perturbTasks[m0.second].loc);
            }            
        } 
    }

    //删除已经匹配的，保留没有匹配的
    // cout<<"M0:"<<M0.size()<<endl;
    // int ttt=0;
    // for(int i=0;i<failWN;i++){
    //     if(mWorkers[failWorkers[i]]!=-1){
    //         ttt++;
    //     }        
    // }
    // cout<<"ttt1:"<<ttt<<endl;

    for(int i=failWorkers.size()-1;i>=0;i--){
        if(mWorkers[failWorkers[i]]!=-1){
            failWorkers[i] = *failWorkers.rbegin();
            failWorkers.pop_back();
        }
    }
    
    
    // ttt=0;
    // for(int i=0 ;i<failTN;i++){
    //     if(mTasks[failTasks[i]]!=-1){
    //         ttt++;
    //     }
    // }
    // cout<<"ttt2:"<<ttt<<endl;

    for(int i=failTasks.size()-1;i>=0;i--){
        if(mTasks[failTasks[i]]!=-1){
            failTasks[i] = *failTasks.rbegin();
            failTasks.pop_back();
        }
    }
    return ans;
}

/**
 * @brief 通过马氏距离计评判基本匹配，越小，越相关，越能够匹配成功，实现时通过小根堆。
 * 
 * @param fileName 
 * @return int 
 */
int oblivious_Ma(string &fileName){
    vector<ma_node> maHeap;//堆的创建
    int workerNum,taskNum,sumNum,ans;
    double scoreTmp;
    read2(fileName,workerNum,taskNum,sumNum);
    for (int i = 0; i < workerNum; i++)
    {
        for (int j = 0; j < taskNum; j++)
        {
            scoreTmp = calDistance3(perturbWorkers[i].loc,perturbTasks[j].loc);
            maHeap.push_back(ma_node(scoreTmp,i,j));
            push_heap(maHeap.begin(),maHeap.end());
        }
        
    }    
    vector<bool> workerUsed(workerNum,false);
    vector<bool> taskUsed(taskNum,false);
    int workerFull=0,taskFull=0,windex,tindex;
    bool wused,tused;
    pair<int,int>m0;
    // while (workerFull < workerNum || taskFull < taskNum)
    // {
    //     pop_heap(maHeap.begin(),maHeap.end());
    //     auto node = maHeap.back();
    //     windex = node.index1;
    //     tindex = node.index2;
    //     wused = workerUsed[windex];
    //     tused = taskUsed[tindex];
    //     if(!wused && !tused){
    //         workerUsed[windex] = true;
    //         taskUsed[tindex] = true;
    //         m0.first = windex;
    //         m0.second = tindex;
    //         M0.push_back(m0);
    //         workerFull++;
    //         taskFull++;
    //         // cout<<node.maScore<<endl;
    //     }
    //     maHeap.pop_back();
    // }
    sort_heap(maHeap.begin(),maHeap.end());
    int count = workerNum*taskNum;
    for (int i = count-1; i > -1; i--)
    {
        if(workerFull >= workerNum || taskFull >= taskNum)break;
        auto node = maHeap.back();
        windex = node.index1;
        tindex = node.index2;
        wused = workerUsed[windex];
        tused = taskUsed[tindex];
        if(!wused && !tused){
            workerUsed[windex] = true;
            taskUsed[tindex] = true;
            m0.first = windex;
            m0.second = tindex;
            M0.push_back(m0);
            workerFull++;
            taskFull++;
            // cout<<node.maScore<<endl;
        }
        maHeap.pop_back();
    }
    
    ans = M0.size();
    return ans;
}

int oblivious_Ma(vector<int>&failWorkers,vector<int>&failTasks){
    vector<ma_node> maHeap;//堆的创建
    int workerNum,taskNum,ans,windex,tindex;
    double scoreTmp;
    workerNum = failWorkers.size();
    taskNum = failTasks.size();
    for (int i = 0; i < workerNum; i++)
    {
        windex = failWorkers[i];
        for (int j = 0; j < taskNum; j++)
        {
            tindex = failTasks[j];
            scoreTmp = calDistance3(perturbWorkers[windex].loc,perturbTasks[tindex].loc);
            maHeap.push_back(ma_node(scoreTmp,windex,tindex));
            push_heap(maHeap.begin(),maHeap.end());
        }
        
    }
    vector<bool> workerUsed(perturbWorkers.size(),false);
    vector<bool> taskUsed(perturbTasks.size(),false);
    int workerFull=0,taskFull=0;
    bool wused,tused;
    pair<int,int>m0;
    sort_heap(maHeap.begin(),maHeap.end());
    int count = workerNum*taskNum;
    vector<pair<int,int>>().swap(M0);//清空原有数据
    //先清除数据
    mWorkers.clear();
    mTasks.clear();
    mWorkers.resize(workerNum,-1);//初始化
    mTasks.resize(taskNum,-1);
    for (int i = count-1; i > -1; i--)
    {
        if(workerFull >= workerNum || taskFull >= taskNum)break;
        auto node = maHeap.back();
        windex = node.index1;
        tindex = node.index2;
        wused = workerUsed[windex];
        tused = taskUsed[tindex];
        if(!wused && !tused){
            workerUsed[windex] = true;
            taskUsed[tindex] = true;
            m0.first = windex;
            m0.second = tindex;
            M0.push_back(m0);
            mWorkers[windex] = tindex;
            mTasks[tindex] = windex;
            workerFull++;
            taskFull++;
            // cout<<node.maScore<<endl;
        }
        maHeap.pop_back();
    }
    //删除匹配成功的
    for(int i=failWorkers.size()-1;i>=0;i--){
        if(mWorkers[failWorkers[i]]!=-1){
            failWorkers[i] = *failWorkers.rbegin();
            failWorkers.pop_back();
        }
    }
    for(int i=failTasks.size()-1;i>=0;i--){
        if(mTasks[failTasks[i]]!=-1){
            failTasks[i] = *failTasks.rbegin();
            failTasks.pop_back();
        }
    }
    ans = M0.size();
    return ans;
}

inline void addEdge2(vector<MNode>& e,vector<int>& head,int u,int v,int w){
    MNode temp;
    //正向边
    ++tot;
    temp.to=v;
    temp.val=w;
    temp.net=head[u];
    head[u]=tot;
    e.push_back(temp);
    //反向边
    ++tot;
    temp.to=u;
    temp.val=0;
    temp.net=head[v];
    head[v]=tot;
    e.push_back(temp);
}
inline void update2(vector<MNode>&e,vector<int>& dis,vector<int>&pre, int& source,int& sink, int&workerNum){
    int x =sink;
    int v,ind=0,wnum=0,indexW=-1,indexT=-1;
    // wnum = perturbWorkers.size();
    wnum = workerNum;
    while (x!=source)//从汇聚节点往源节点进行更新
    {
        v = pre[x];
        e[v].val-=dis[sink];
        e[v^1].val+=dis[sink];
        x=e[v^1].to;
        ind = e[v].to;
        //记录匹配成功的工作者和任务编号
        if ( ind > 1 && ind < wnum+2){
            indexW = ind-2;//减2恢复原来编号
        }else{
            indexT = ind-wnum-2;
        }
        if(indexW!=-1&&indexT!=-1){
            mWorkers[indexW]=indexT;
            mTasks[indexT] = indexW;
            indexW=-1;
            indexT=-1;
        }
    }
    ans+=dis[sink];
}
inline int bfs2(vector<MNode>& e, vector<int>& dis,vector<int>&pre, vector<int>& vist,vector<int>& head,int& source,int& sink){
    vist.assign(vist.size(),0);
    int x,v;
    queue<int>q;
    q.push(source);
    vist[source]=1;
    dis[source]=INF;
    while (!q.empty())
    {
        x = q.front();//获取队列头部
        q.pop();
        for (int i = head[x]; i ; i=e[i].net )
        {
            if(e[i].val==0) continue;//只关心流量剩余量大于0
            v=e[i].to;
            if(vist[v]==1) continue;//访问过就不访问了
            dis[v]=min(dis[x],e[i].val);
            pre[v]=i;//记录前驱，方便修改边权 
            q.push(v);
            vist[v]=1;//标记访问
            if(v==sink) return 1;//访问到源节点
        }
        
    }
    
    return 0;
}
//组内重新分配
int g_M(int&gsize,vector<pair<int,int>>&g,vector<pair<int,int>>&Mg,vector<int>&failWorkers,vector<int>&failTasks){
    tot = 1;
    ans = 0;
    int workerNum,taskNum,sumNum;
    workerNum = workerLists.size();
    taskNum = taskLists.size();
    
    sumNum = workerNum+taskNum+3;//加3原因是0下标不用
    vector<int>vist(sumNum,0);
    vector<int>dis(sumNum,0);
    vector<int>pre(sumNum,0);
    vector<int>head(sumNum,0);
    vector<MNode>e(2);
    mWorkers.clear();
    mTasks.clear();
    mWorkers.resize(workerNum,-1);//初始化
    mTasks.resize(taskNum,-1);
    
    int source=1,sink=source+workerNum+taskNum+1;
    for (int i = 0; i < gsize; i++)
    {
        addEdge2(e,head,source,g[i].first+2,1);
    }
    for (int i = 0; i < gsize; i++)
    {
        int windex = g[i].first;
        for (int j = 0; j < gsize; j++)
        {
            int tindex = g[j].second;
            if (satisfyDistanceTime(workerLists[windex],taskLists[tindex]))
            // if (secureDistanceCalB(windex,tindex))
            {
                addEdge2(e,head,windex+2,tindex+workerNum+1+1,1);//0号不用，1号下表存源节点，因此二分图左边第一个点下标为i+2，右边节点的第一个下标j+workerNum+1+1
            }
            
        }

    }

    for (int i = 0; i < gsize; i++)
    {
        addEdge2(e,head,g[i].second+workerNum+1+1,sink,1);
    }
    //开始匹配
    while (bfs2(e,dis,pre,vist,head,source,sink)!=0)
    {
        update2(e, dis, pre, source, sink, workerNum);
    }
    // 找出匹配成功的
    if(workerNum<taskNum){
        for(int i=0;i<workerNum;i++){
            if(mWorkers[i]!=-1){
                pair<int,int> m0;
                m0.first=i;
                m0.second=mWorkers[i];
                Mg.push_back(m0);//记录匹配对
            }            
        } 
    }else{
        for(int i=0;i<taskNum;i++){
            // cout<<mTasks[i]<<endl;
            if(mTasks[i]!=-1){
                pair<int,int> m0;
                m0.first=mTasks[i];
                m0.second=i;
                Mg.push_back(m0);//记录匹配对
                // cout<<"("<<mTasks[i]<<","<<i<<") ";
            }            
        } 
    }
    
    //没有匹配成功的
    for (int i = 0; i < gsize; i++)
    {
        if(mWorkers[g[i].first]==-1){
            // if(count(failWorkers.begin(),failWorkers.end(),g[i].first)==0)//保证唯一
                failWorkers.push_back(g[i].first);
            // else{
                // cout<<"w:"<<g[i].first<<endl;
                //  vector<int>::iterator iter = find(failWorkers.begin(),failWorkers.end(),g[i].first);
                //  cout<<"ddd:"<<g[i].first<<" "<<(*iter)<<endl;
            // }
            // cout<<"w:"<<g[i].first<<" ";
           
        }
        if(mTasks[g[i].second]==-1){
            // if(count(failTasks.begin(),failTasks.end(),g[i].second)==0)
                failTasks.push_back(g[i].second);
            // else{
                // cout<<"t:"<<g[i].second<<endl;
            // }
            // cout<<"t:"<<g[i].second<<" ";

        }
    }
    return ans;
}